<?php

class Point
{

    public function __construct($x, $y)
    {
        $this->x = (int)$x;
        $this->y = (int)$y;
    }
    public $x;
    public $y;
}

class Size
{

    public function __construct($width, $height)
    {
        $this->width = (int)$width;
        $this->height = (int)$height;
    }
    public $width;
    public $height;
}

class Bounds
{

    public function __construct(Point $location, Size $size)
    {
        $this->location = $location;
        $this->size = $size;
    }
    public $location;
    public $size;

    public function getSurface()
    {
        return $this->size->width * $this->size->height;
    }
}

// Input entry to place in the grid.
class GridEntry
{

    public function __construct($weight, $entry)
    {
        $this->weight = $weight;
        $this->entry = $entry;
    }
    // The weight is a number between 0 and 1.
    public $weight;
    // Title of the article, if any.
    public $entry;
}

// Output item of the grid.
class GridNewnit
{
    // Location of the newnit.
    public $bounds;
    // Source grid entry.
    public $gridEntry;
}

/**
 * Used to layout grid entries into the grid.
 * @author panosbaroudjian
 *
 */
class GridLayouter
{
    private $newnits;
    private $grid;
    private $entries;
    private $wildZones;
    private $totalWeight;
    private $totalSize;

    /**
     * Comparison function for sorting
     */
    public static function entryCompare($e1, $e2)
    {
        return $e1->weight > $e2->weight;
    }
    
    /**
     * Comparison function for sorting
     */
    public static function entryCompareReverse($e1, $e2)
    {
        return $e1->weight < $e2->weight;
    }
    
    private static function wildZoneCompare($w1, $w2)
    {
        return $w1->getSurface() > $w2->getSurface();
    }

	private function cloneArray($arr)
	{
		$newArr = array();
		foreach ($arr as $item)
			$newArr[] = $item;
		return $newArr;
	}
	
    /// Try to place the remaining entries in the grid.
    public function tryPlace()
    {
        // Stopping condition: all entries has been placed successfully.
        if (count($this->entries) == 0)
			if (count($this->wildZones) > 0)
				return 0;
			else
				return 0;
             // Stopping condition: there is no wild zone to place the entry.
        if (count($this->wildZones) == 0)
            return -1;
             // We grab the largest entry.
        $localEntry = array_pop($this->entries);
		
		
		//wild zones merging
		$rebWZ = array();
		$merged = array();
		for ($i = 0; $i < count($this->wildZones); $i++)
		{
			$wz1 = $this->wildZones[$i];
			
			if (isset($merged[$i]))
				continue;
			for ($j = $i + 1; $j < count($this->wildZones); $j++)
			{
				$wz2 = $this->wildZones[$j];
				if (isset($merged[$j]))
					continue;
			
				if ($wz1->location->x == $wz2->location->x && $wz1->size->width == $wz2->size->width)
				{
					if ($wz2->location->y == $wz1->location->y + $wz1->size->height)
					{
						$merged[$i] = true;
						$merged[$j] = true;
						$rebWZ[] = new Bounds(new Point($wz1->location->x, $wz1->location->y), new Size($wz1->size->width, $wz1->size->height + $wz2->size->height));
						break;
					}
					if ($wz1->location->y == $wz2->location->y + $wz2->size->height)
					{
						$merged[$i] = true;
						$merged[$j] = true;
						$rebWZ[] = new Bounds(new Point($wz2->location->x, $wz2->location->y), new Size($wz1->size->width, $wz1->size->height + $wz2->size->height));
						break;
					}
				}
				if ($wz1->location->y == $wz2->location->y && $wz1->size->height == $wz2->size->height)
				{
					if ($wz2->location->x = $wz1->location->x + $wz1->size->width)
					{
						$merged[$i] = true;
						$merged[$j] = true;
						$rebWZ[] = new Bounds(new Point($wz1->location->x, $wz1->location->y), new Size($wz1->size->width + $wz2->size->width, $wz1->size->height));
						
						break;
					}
					if ($wz1->location->x = $wz2->location->x + $wz2->size->width)
					{
						$merged[$i] = true;
						$merged[$j] = true;
						$rebWZ[] = new Bounds(new Point($wz2->location->x, $wz2->location->y), new Size($wz2->size->width + $wz1->size->width, $wz1->size->height));
						
						break;
					}
					
				}
			}
			if (!isset($merged[$i]))
			{
				$rebWZ[] = $wz1;
				$merged[$i] = true;
			}
		}
		
		$this->wildZones = $rebWZ;
		
		
        $wildZone = array_pop($this->wildZones);
		
		// Backup wildZone if we are fucked up
		$wildZoneBackup = $this->cloneArray($this->wildZones);
		
        //$bounds = clone $wildZone;
        // We guess the target size.
        $localSize = new Size(
            ceil(pow(($localEntry->weight / $this->totalWeight), 1 / 2) * (float)$this->totalSize->width),
            ceil(pow(($localEntry->weight / $this->totalWeight), 1 / 2) * (float)$this->totalSize->height));
			
		if ($localEntry->entry == null)
			$localSize = new Size(3, 1);
			
        // We clamp if we're outer the wild zone.
        if ($localSize->width > $wildZone->size->width)
            $localSize->width = $wildZone->size->width;
        if ($localSize->height > $wildZone->size->height)
            $localSize->height = $wildZone->size->height;
			
		// Contra-clamp if we're lonely
		if (count($this->entries) == 0)
		{
			$localSize->width = $wildZone->size->width;
			$localSize->height = $wildZone->size->height;
		}
		
        $nwzCount = 0;
        $lastResult = 0;
        // Main loop: we try to place the entry and the subentries
        // until it all fits nicely
        do
        {
            // Clean wildzones that do not worked.
            /*while ($nwzCount > 0)
            {
                array_pop($this->wildZones);
                $nwzCount--;
            }*/
            if ($lastResult != 0)
            {
				// Restore the backup because wildzones may be fucked up.
				//var_dump("restoring");
				$this->wildZones = $this->cloneArray($wildZoneBackup);
                if ($lastResult < 0)
                {
                    if ($localSize->width > $localSize->height)
                        $localSize->width--;
                    else
                        $localSize->height--;
                }
                else
                {
					// Never called in the actual version of the algorithm
					// because it caused an infinite loop with the reduction algo (just upwards)
                    if ($localSize->width < $localSize->height && $localSize->width < $wildZone->size->width)
                        $localSize->width++;
                    elseif ($localSize->height < $wildZone->size->height)
                        $localSize->height++;
					else
					{
						//var_dump($this->wildZones);
						return 0;
					}
                }
                if ($localSize->width == 0 || $localSize->height == 0)
                {
                    // Just restore the entry and wild zones
                    array_push($this->entries, $localEntry);
                    //array_push($this->wildZones, $wildZone);
                    return -1;
                }
            }
            // We create new wild zones in the gaps.
            $nwzCount = 0;
            $newWildZones = array();
            // Check whether it's better to split horizontally or vertically
            $splitDirection = ($wildZone->size->width) * ($wildZone->size->height -
                                         $localSize->height) >
                                         ($wildZone->size->width -
                                         $localSize->width) *
                                         ($wildZone->size->height);
            if ($localSize->height < $wildZone->size->height)
            {
                // Horizontal wild zone.
                $newWildZone = new Bounds(
                    new Point($wildZone->location->x, $wildZone->location->y + $localSize->height),
                    new Size($splitDirection ? $wildZone->size->width : $localSize->width,
                        $wildZone->size->height - $localSize->height));
                array_push($newWildZones, $newWildZone);
                $nwzCount++;
            }
            if ($localSize->width < $wildZone->size->width)
            {
                // Vertical wild zone (does not go to the bottom of the wildzone).
                $newWildZone = new Bounds(
                    new Point($wildZone->location->x + $localSize->width, $wildZone->location->y),
                    new Size($wildZone->size->width - $localSize->width,
                        $splitDirection ? $localSize->height : $wildZone->size->height));
                array_push($newWildZones, $newWildZone);
                $nwzCount++;
            }
			// We place the largest on the top
            usort($newWildZones, 'GridLayouter::wildZoneCompare');
            foreach ($newWildZones as $newWildZone)
            {
                array_push($this->wildZones, $newWildZone);
            }
            //$nwzCount--;
            $lastResult = $this->tryPlace();
        }
        while ($lastResult != 0);
        $localNewnit = new GridNewnit();
        $localNewnit->bounds = new Bounds($wildZone->location, $localSize);
        $localNewnit->gridEntry = $localEntry;
        array_push($this->newnits, $localNewnit);
        return 0;
    }

    /**
     * Launches the layouting algorithm
     * @param mixed $entries The entries to be sorted
     * @param Size $gridSize The size of the grid
     * @return array: The newnits with the new layout
     */
    public function layout($entries, $gridSize)
    {
        $this->newnits = array();
        $this->grid = array();
        $this->entries = $entries;
        usort($this->entries, 'GridLayouter::entryCompare');
        foreach ($this->entries as $entry)
        {
            $this->totalWeight += $entry->weight;
        }
		
		// We push the logo
		array_push($this->entries, new GridEntry(1.0, null));
		
        $this->totalSize = $gridSize;
        // We start with the first entry and we want to fill the whole grid
        $this->wildZones = array(new Bounds(new Point(0, 0), clone $gridSize));
        $this->tryPlace();
        return $this->newnits;
    }
}
